We consider the problem of network coding across three unicast sessions overa directed acyclic graph, when each session has min-cut one. Previous work byDas et al. adapted a precoding-based interference alignment technique,originally developed for the wireless interference channel, specifically tothis problem. We refer to this approach as precoding-based network alignment(PBNA). Similar to the wireless setting, PBNA asymptotically achieves half theminimum cut; different from the wireless setting, its feasibility depends onthe graph structure. Das et al. provided a set of feasibility conditions forPBNA with respect to a particular precoding matrix. However, the set consistedof an infinite number of conditions, which is impossible to check in practice.Furthermore, the conditions were purely algebraic, without interpretation withregards to the graph structure. In this paper, we first prove that the set ofconditions provided by Das. et al are also necessary for the feasibility ofPBNA with respect to any precoding matrix. Then, using two graph-relatedproperties and a degree-counting technique, we reduce the set to just fourconditions. This reduction enables an efficient algorithm for checking thefeasibility of PBNA on a given graph.
展开▼
